﻿using System;

class BinarySearch
{
    static void Main()
    {
        //Exercise 11.
        //Write a program that finds the index of given element in a sorted array of integers by using the binary search algorithm 
        //(find it in Wikipedia).

        //int[] array = { 1, 2, 3, 4, 9, 10, 11, 13, 14, 25, 28, 34, 74 };

        //enter the length and the elements of the array from the console
        Console.Write("Type the length of the array (N):  ");
        int N = int.Parse(Console.ReadLine());
        Console.WriteLine("Type the elements of the array:");
        int[] array = new int[N];
        for (int i = 0; i < N; i++)
        {
            array[i] = int.Parse(Console.ReadLine());
        }
        
        Array.Sort(array);       

        int halfLength = array.Length / 2;
        
        int key = int.Parse(Console.ReadLine());        

        if (key > array[array.Length - 1] || key < array[0])        //check if the key is within the array at all
        {
            Console.WriteLine("The key is out of the scope of the array.");
            return;
        }

        for (int i = 0; i <= halfLength; i++)
        {
            if (key == array[i])
            {
                Console.WriteLine("The index is: {0}", i);
                return;
            }
            else if (key > array[i])
            {
                halfLength = halfLength + (halfLength / 2);
                continue;
            }
            else if (key < array[i])
            {
                halfLength = halfLength / 2;
                continue;
            }        
        }        
        Console.WriteLine("The key is not present in the arrey.");
    }
}

